#include <stdio.h>
#include <stdbool.h>

#define N 10000
bool is_prime[N];
int prime[N];

int main()
{
    int cnt = 0;
    for(int i = 2;i<=N;++i)
    {
        if(!is_prime[i])
            prime[cnt++] = i;
        for(int j = 0;prime[j]*i<=N;++j)
        {
            is_prime[prime[j]*i] = true;
            if(i%prime[j] == 0)
            {
                 break;
            }
        }
    }
    for(int i = 0;i<cnt;++i)
    {
        printf("%d:%d\n",i,prime[i]);
    }
    return 0;
}
